package org.xqh.study.leetcode.algorithm.twopointer;

/**
 * @ClassName CharacterReplacement
 * @Description 替换后的最长重复字符
 * https://leetcode-cn.com/problems/longest-repeating-character-replacement/
 * @Author xuqianghui
 * @Date 2021/2/12 22:37
 * @Version 1.0
 */
public class CharacterReplacement {

    public static void main(String[] args) {
        String s = "AABABBA";
        System.out.println(characterReplacement(s, 1));
    }


    /**
     * 最长连续字符 包含k+1个 不同字符  本次 提交 6ms
     *
     * 右指针向右移动 找到满足条件的 位置,
     * 右指针 移动到不满足位置时 暂停,
     *  左指针开始移动一格, 右边界继续移动.
     *
     * @param s
     * @param k
     * @return
     */
    public static int characterReplacement(String s, int k) {
        int res = 0;
        char[] arr = s.toCharArray();
        int len = arr.length;
        int left = 0;
        int right = 0;
        int[] freq = new int[128];
        int count = 0;
        int maxNum = 0;//相同字符出现最多的 次数

        while (right < len) {
            count++;
            freq[arr[right]]++;
            if (freq[arr[right]] > maxNum) {
                maxNum = freq[arr[right]];
            }
            right++;

            if (count - maxNum <= k) {
                res = Math.max(res, right - left);
            }
            /**
             * 这里  右边界出现 不满足情况, 左边界只需要移动一次.
             * 因为  如果 移动一次还不满足的话, 在移动两次 就算满足 也不是 最长的 情况.
             */
            if (count - maxNum > k) {//左边 指针移动
                count--;
                freq[arr[left]]--;
                left++;
            }
        }
        return res;
    }

    /**
     * 他人提交 代码 3ms
     *
     * @param s
     * @param k
     * @return
     */
    public static int characterReplacement22(String s, int k) {
        int[] nums = new int[128];
        int n = s.length(), left = 0, right = 0, maxn = 0;
        char[] cs = s.toCharArray();
        while (right < n) {
            if (maxn < ++nums[cs[right]]){
                maxn = nums[cs[right]];
            }
            if (right++ - left + 1 - maxn > k) {
                nums[cs[left++]]--;
            }
        }
        return right - left;
    }


}
